class Solution
{
public:
    int countPalindromicSubsequence(string s)
    {
        int n = s.size();
        int result = 0;
        for (char ch = 'a'; ch <= 'z'; ++ch)
        {
            int chFirstOccur = 0, chLastOccur = n - 1;
            while (chFirstOccur < n && s[chFirstOccur] != ch)
            {
                ++chFirstOccur;
            }
            while (chLastOccur >= 0 && s[chLastOccur] != ch)
            {
                --chLastOccur;
            }
            if (chLastOccur - chFirstOccur < 2)
            {
                continue;
            }
            int existChar = 0;
            int existCount = 0;
            for (int k = chFirstOccur + 1; k < chLastOccur; ++k)
            {
                if (!(existChar & (1 << (s[k] - 'a'))))
                {
                    ++existCount;
                    existChar |= (1 << (s[k] - 'a'));
                }
            }
            result += existCount;
        }
        return result;
    }

    // 下面两种都在最后一个用例超时
    int countPalindromicSubsequence(string s)
    {
        int existChar = 0;
        unordered_map<char, int> frontParts;
        unordered_set<string> result;
        for (char c : s)
        {
            for (char middle = 'a'; middle <= 'z'; ++middle)
            {
                if (frontParts[c] & (1 << (middle - 'a')))
                {
                    result.insert({c, middle, c});
                }
            }
            for (char first = 'a'; first <= 'z'; ++first)
            {
                if (existChar & (1 << (first - 'a')))
                {
                    frontParts[first] |= 1 << (c - 'a');
                }
            }
            existChar |= 1 << (c - 'a');
        }
        return result.size();
    }

    int countPalindromicSubsequence(string s)
    {
        int existChar = 0;
        unordered_map<char, unordered_set<string>> frontParts;
        unordered_set<string> result;
        for (char c : s)
        {
            for (auto &frontPart : frontParts[c])
            {
                result.insert(frontPart + c);
            }
            for (char first = 'a'; first <= 'z'; ++first)
            {
                if (existChar & (1 << (first - 'a')))
                {
                    frontParts[first].insert(string() + first + c);
                }
            }
            existChar |= 1 << (c - 'a');
        }
        return result.size();
    }
};